package algorithm.递归求组合;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 递归求组合，例如从 [0,1,2,,3,4] 中取4个数
 *
 * 正确结果是：
 * 0,1,2,3
 * 0,1,2,4
 * 0,1,3,4
 * 0,2,3,4
 * 1,2,3,4
 *
 */
class Solution {

    public static void main(String[] args) {
        List<List<Integer>> list = new Solution().combine(5, 4);
        //输出结果
        for (List<Integer> ll : list) {
            List<String> ss = ll.stream().map(i -> i.toString()).collect(Collectors.toList());
            System.out.println(String.join(",", ss));
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> valueList = new ArrayList<List<Integer>>();//结果
        boolean jud[] = new boolean[n];//用于判断是否使用
        dfs(-1, k, valueList, jud, n);
        return valueList;
    }

    private void dfs(int index, int count, List<List<Integer>> valueList, boolean jud[], int n) {
        //k个元素满
        if (count == 0) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<jud.length;i++){
                if(jud[i]){
                    list.add(i);
                }
            }
            valueList.add(list);
        } else {
            //只能在index后遍历 回溯向下
            for (int i = index + 1; i < n; i++) {
                jud[i] = true;
                dfs(i, count - 1, valueList, jud, n);
                jud[i] = false;//还原
            }
        }
    }
}
